##矩阵快速幂算法（递归法
def matrix_mul(A, B):
#矩阵乘法函数，返回两个矩阵相乘的值
    return [[sum(a * b % 99999999 for a, b in zip(col, row)) % 99999999 for col in zip(*B)] for row in A]

def matrix_pow(A, n):
    size_ = len(A)
    if n == 0:#返回单位矩阵
        res = [[0 for _ in range(size_)] for _ in range(size_)]
        for i in range(size_):
            res[i][i] = 1
        return res
    elif n == 1:#返回自己
        return A
    else:
        y = matrix_pow(A, n // 2)
        if n & 1:#要乘
            return matrix_mul(matrix_mul(y, y), A)
        return matrix_mul(y, y)

